#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2025/3/24
# @USER    : Shengji He
# @File    : FindClosestPalindrome.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
"""
- Math
- String
"""

class Solution:
    """
    [564. Find the Closest Palindrome](https://leetcode.com/problems/find-the-closest-palindrome/description/)

    Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

    The closest is defined as the absolute difference minimized between two integers.

    Example 1:
        Input: n = "123"
        Output: "121"

    Example 2:
        Input: n = "1"
        Output: "0"
        Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.


    Constraints:
        - 1 <= n.length <= 18
        - n consists of only digits.
        - n does not have leading zeros.
        - n is representing an integer in the range [1, 10^18 - 1].
    """

    def nearestPalindromic(self, n: str) -> str:
        length = len(n)

        half = (length + 1) // 2
        start = length % 2

        out = None
        diff = None
        for i, num in enumerate([1, 0, -1]):
            half_str = str(int(n[:half]) + num)
            if len(half_str) > half:
                start += 1
            elif len(half_str) < half:
                start -= 1
                if start < 0:
                    half_str += '9'
                    start = 1
            elif int(half_str) == 0 and length == 2:
                start = 1
                half_str = '9'
            cur_out = half_str + half_str[::-1][start:]
            cur_diff = abs(int(cur_out) - int(n))
            if i == 0:
                out = cur_out
                diff = cur_diff
            else:
                if cur_diff == 0:
                    continue
                if cur_diff <= diff:
                    diff = cur_diff
                    out = cur_out
        return out

    def nearestPalindromic_ai(self, n: str) -> str:
        s = n
        length = len(s)

        if length == 1:
            num = int(s)
            candidates = []
            if num > 0:
                candidates.append(str(num - 1))
            candidates.append(str(num + 1))
            candidates.append('0')  # Ensure '0' is considered for n="1"
            valid = [c for c in candidates if c != s]
            valid.sort(key=lambda x: (abs(int(x) - num), int(x)))
            return valid[0] if valid else '0'

        candidates = []
        k = (length + 1) // 2
        prefix = s[:k]

        # Generate mirror candidate
        mirror_candidate = self.generate_mirror(length, prefix)
        if mirror_candidate != s:
            candidates.append(mirror_candidate)

        # Generate plus and minus candidates
        prefix_num = int(prefix)
        plus_prefix = str(prefix_num + 1)
        plus_candidate = self.generate_mirror(length, plus_prefix)
        candidates.append(plus_candidate)

        minus_prefix = str(prefix_num - 1)
        minus_candidate = self.generate_mirror(length, minus_prefix)
        candidates.append(minus_candidate)

        # Generate floor candidate (max n-1 digits palindrome)
        if length > 1:
            floor_candidate = '9' * (length - 1)
            candidates.append(floor_candidate)

        # Generate ceil candidate (min n+1 digits palindrome)
        ceil_candidate = '1' + '0' * (length - 1) + '1'
        candidates.append(ceil_candidate)

        # Filter valid candidates (no leading zeros and not equal to original)
        valid_candidates = []
        for candidate in candidates:
            if candidate and candidate != s:
                if candidate[0] != '0' or candidate == '0':
                    valid_candidates.append(candidate)

        # Handle case where all candidates are filtered out (unlikely due to constraints)
        if not valid_candidates:
            return ''

        # Find the closest candidate
        num = int(s)
        closest = None
        min_diff = float('inf')
        for candidate in valid_candidates:
            candidate_num = int(candidate)
            diff = abs(candidate_num - num)
            if diff < min_diff:
                min_diff = diff
                closest = candidate_num
            elif diff == min_diff:
                if candidate_num < closest:
                    closest = candidate_num
        return str(closest)

    def generate_mirror(self, original_length: int, new_prefix: str) -> str:
        n = original_length
        k = (n + 1) // 2

        # Adjust new_prefix to have exactly k digits, padding with zeros if necessary
        new_prefix_str = new_prefix.zfill(k)
        if len(new_prefix_str) > k:
            new_prefix_str = new_prefix_str[:k]

        # Generate the mirrored string
        if n % 2 == 0:
            return new_prefix_str + new_prefix_str[::-1]
        else:
            return new_prefix_str + new_prefix_str[:-1][::-1]


if __name__ == '__main__':
    # n = "1"
    # n = "10"
    # n = "100"
    # n = "1000"
    # n = "999"
    n = "100001"

    S = Solution()
    print(S.nearestPalindromic(n))
    print(S.nearestPalindromic_ai(n))
    print('done')
